Luồng cực đại là gì? Các công bố khoa học về Luồng cực đại

Luồng cực đại (Maximum Flow) là một khái niệm trong lý thuyết đồ thị. Nó liên quan đến việc tìm cách lưu lượng truyền qua một mạng lưới từ một đỉnh nguồn (source) đến một đỉnh đích (sink) sao cho lưu lượng này là lớn nhất có thể.

Trong một mạng lưới, các đỉnh biểu thị vị trí và các cạnh biểu thị đường truyền thông giữa các vị trí đó. Mỗi cạnh có một số liệu gọi là khả năng chứa lưu lượng (capacity) - tức là lưu lượng tối đa có thể truyền qua cạnh đó.

Luồng cực đại tìm cách phân phối lưu lượng từ đỉnh nguồn đến đỉnh đích sao cho:
1. Lưu lượng trên mỗi cạnh không vượt quá khả năng chứa của cạnh đó.
2. Tổng lưu lượng đi qua mạng lưới là lớn nhất.

Để tìm luồng cực đại, các thuật toán như thuật toán Ford-Fulkerson hoặc thuật toán Edmonds-Karp được sử dụng. Các thuật toán này đều dựa trên khái niệm "đường cắt" (cut) trong đồ thị và sử dụng việc tăng cường đường đi (augmenting path) để tăng giá trị lưu lượng truyền qua mạng lưới.
Để hiểu chi tiết hơn về luồng cực đại, ta cần biết thêm một số khái niệm và thuật ngữ liên quan.

1. Đồ thị mạng (Network graph): Đồ thị mạng được sử dụng để biểu diễn một hệ thống hay mạng gồm các vị trí (đỉnh) và các đường truyền thông (cạnh) giữa chúng. Đồ thị mạng bao gồm một đỉnh nguồn (s) và một đỉnh đích (t), cùng với các đỉnh và cạnh khác.

2. Khả năng chứa lưu lượng (Capacity): Mỗi cạnh trong đồ thị mạng có một giá trị thể hiện lưu lượng tối đa mà cạnh đó có thể truyền qua. Đây là một giá trị không âm và có thể khác nhau cho từng cạnh.

3. Luồng (Flow): Một luồng trên đồ thị mạng là một phân phối của lưu lượng từ đỉnh nguồn đến đỉnh đích qua các cạnh. Luồng trên một cạnh phải thỏa mãn các ràng buộc sau:
- Không vượt quá khả năng chứa của cạnh: Lưu lượng trên mỗi cạnh phải nhỏ hơn hoặc bằng khả năng chứa của cạnh đó.
- Cân bằng luồng tại các đỉnh ngoại trừ đỉnh nguồn và đích: Tổng lưu lượng đến một đỉnh (trừ đỉnh nguồn và đích) phải bằng tổng lưu lượng ra khỏi đỉnh đó.

4. Luồng cực đại (Maximum Flow): Luồng cực đại trên một đồ thị mạng là luồng có tổng lưu lượng trên các cạnh là lớn nhất có thể. Điều này có nghĩa là không thể tăng giá trị của luồng bằng cách phân phối lưu lượng khác.

Thuật toán Ford-Fulkerson và Edmonds-Karp là hai phương pháp được sử dụng để tìm luồng cực đại trên đồ thị mạng. Cả hai thuật toán này đều dựa trên việc tìm đường đi từ đỉnh nguồn đến đỉnh đích (đường cắt) có thể cung cấp một lượng lưu lượng khả dụng tiếp theo để tăng giá trị của luồng. Thuật toán tiếp tục tìm kiếm đường đi này và tăng giá trị lưu lượng cho đến khi không còn đường đi nữa. Khi đó, luồng đã đạt đến cực đại.

Luồng cực đại có ứng dụng trong nhiều lĩnh vực như mạng máy tính, điều độ giao thông, lập lịch công việc, v.v.